package GFAlgorithm;

public class GFAlgorithm implements GFAlgorithmInterface {
    @Override
    public int addOrMinus(int a, int b) {
        return a ^ b;
    }

    @Override
    public int multiply(int a, int b, int poly) {
        int result = 0;
        while (b > 0) {
            if (b % 2 == 1) {
                result = result ^ a;
            }
            a = gmul(a, poly);
            b >>= 1;
        }
        return result;
    }

    @Override
    public int divide(int a, int b) {
        // lenA和lenB分别表示2进制格式下a和b的长度，lenDist为两个长度的差
        int lenA = getBitLength(a);
        int lenB = getBitLength(b);
        int lenDist = lenA - lenB + 1;
        // 被除数位数小于除数
        if (lenDist < 1) return 0;
        // 被除数位数等于除数
        if (lenDist == 1) return 1;
        // 被除数位数大于除数（除了以上两种情况，就剩下这种情况了）
        int div = 0;
        while (lenA >= lenB) {
            a = a ^ (b << (lenA - lenB));
            div = div ^ (1 << (lenA - lenB));
            lenA = getBitLength(a);
        }

        return div;
    }

    @Override
    public int euclid(int a, int b) {
        int temp = 0;
        while (b != 0) {
            temp = mod(a, b);
            a = b;
            b = temp;
        }
        return a;
    }

    @Override
    public int[] exEuclid(int a, int b) {
        if (b == 0) {
            return new int[]{a, 1, 0};
        }
        int[] res = exEuclid(b, mod(a, b));
        int x = res[2];
        int y = res[1] ^ multiply(divide(a, b), res[2], 283);
        return new int[]{res[0], x, y};
    }

    @Override
    public int inverseMod(int a, int m) {
        int[] res = exEuclid(a, m);
        return res[1];
    }

    private int gmul(int a, int poly) {
        a <<= 1;
        if ((a & 0x100) == 0x100) {
            a = a ^ poly;
        }

        return a & 0xff;
    }

    private int mod(int a, int b) {
        // lenA和lenB分别表示2进制格式下a和b的长度，lenDist为两个长度的差
        int lenA = getBitLength(a);
        int lenB = getBitLength(b);
        int lenDist = lenA - lenB + 1;
        // 被除数位数小于除数
        if (lenDist < 1) return a;
        // 被除数位数等于除数
        if (lenDist == 1) return a ^ b;
        // 被除数位数大于除数（除了以上两种情况，就剩下这种情况了）
        while (lenA >= lenB) {
            a = a ^ (b << (lenA - lenB));
            lenA = getBitLength(a);
        }
        return a;
    }

    private int getBitLength(int num) {
        if (num == 0) return 0;
        return Integer.toBinaryString(num).length();
    }
}
